درسنامه آموزشی فصل اول ریاضیات گسسته کلاس دوازدهم ریاضی

نقش استدلال در زندگی انسان‌ها انکارناپذیر است. همهٔ ما در زندگی روزمره و یا در زندگی حرفه‌ای خود نیازمند کسب توانمندی در این زمینه هستیم. تسلیم عقل در برابر استدلال موهبتی الهی است که امکان تعامل بین انسان‌ها و توسعه علوم گوناگون و رشد و بالندگی را در زمینه‌های مختلف برای بشر فراهم ساخته است. استدلال و اثبات در ریاضیات نیز جایگاه ویژه‌ای دارد.

درک و فهم ریاضی بدون توجه به استدلال امکان ندارد و آموزش ریاضیات را محدود به حفظ کردن رویّه‌ها و الگوریتم‌ها خواهد کرد. آشنایی با روش‌های استدلال و اثبات در ریاضیات، هم به فهم ریاضیات و هم به بسط و توسعه آن کمک شایانی می‌نماید. هدف ما در این درس آشنایی با برخی از روش‌های استدلال و اثبات در ریاضی است.

مثال: درستی یا نادرستی گزاره‌های زیر را بررسی کنید:

الف) مجموع سه عدد طبیعی متوالی بر 3 بخش‌پذیر است.
ب)‌ عدد ${{2}^{{{2}^{n}}}}+1$ به‌ازای همهٔ عددهای طبیعی n، عددی اول است.

حل: گاهی ممکن است برای فهم یک گزاره، مثال‌هایی را برای صدق آن بررسی کنیم.
برای نمونه برای گزاره الف داریم:

$5+6+7=18$
$10+11+12=33$
$25+26+27=78$
$31+32+33=96$

در همه موارد حاصل جمع‌های به‌دست آمده، درستی گزاره الف را نشان می‌دهند همچنین برای $n=1$، $n=2$، $n=3$ و $n=4$ حاصل ${{2}^{{{2}^{n}}}}+1$ به ترتیب برابر 5، 17، 257 و 65537 است که همگی اعداد اول هستند و ظاهراً بر درستی گزاره ب دلالت می‌کنند.

آیا ارائه این مثال‌ها برای برقراری گزاره‌های الف و ب کافی هستند، اگر کافی نیست آیا ارائه مثال‌های بیشتر کفایت می‌کند؟

در مورد الف هر چقدر مثال ارائه کنید، مشاهده خواهید کرد که گزاره برقرار است، اما در مورد گزاره ب، $n=5$ آن‌گاه:

${{2}^{{{2}^{n}}}}+1=4294967297=641\times 6700417$

که به وضوح نشان می‌دهد، حاصل یک عدد اول نیست. همین «مثال نقض» نشان می‌دهد که گزارهٔ ب در حالت کلی درست نیست. این روش استدلال به‌صورت معمول برای رد کردن یک حکم کلی به کار می‌رود و استدلال به‌کمک «مثال نقض» است.

در مورد گزاره الف با اینکه نمی‌توانید مثال نقضی ارائه کنید، امّا درستی گزاره با ارائه مثال به‌دست نمی‌آید. مثلاً یک احتمال این است که نتوانید مثال نقضی ارائه کنید و یا اینکه تاکنون مثال نقضی برای آن ارائه نشده باشد. به هر حال در اینجا اثبات دشوار نیست. کافی است سه عدد طبیعی را با n، $n+1$ و $n+2$ نمایش دهیم. در این‌صورت داریم:

$n+n+1+n+2=3n+3=3\left( n+1 \right)$

که نشان می‌دهد گزاره الف در حالت کلی درست است.

این نوع اثبات کردن را «اثبات مستقیم» می‌نامند. البته اثبات مستقیم ممکن است کاملاً پیچیده باشد. هدف این کتاب طرح اثبات‌های دشوار نیست. محتوای آموزش این درس در چارچوب مطالبی است که تاکنون آموخته‌اید. در کار در کلاس نمونه‌هایی از استدلال به روش «اثبات مستقیم» و استدلال به‌کمک «مثال نقض» را مشاهده خواهید کرد.

اثبات با در نظر گرفتن همه حالت‌ها

گاهی برای اثبات یک گزاره لازم است همهٔ موارد ممکن در مورد مسئله را درنظر بگیریم. به مثال زیر توجه کنید.

مثال: ثابت کنید برای هر عدد طبیعی n، ${{n}^{2}}-5n+7$ عددی فرد است.

حل: دو حالت در اینجا ممکن است رخ دهد:

الف) n زوج است، به‌عبارت دیگر $\left( k\in \mathbb{N} \right)\,n=2k$؛ در این حالت داریم: 

${{n}^{2}}-5n+7={{\left( 2k \right)}^{2}}-5\left( 2k \right)+7=4{{k}^{2}}-10k+6+1$

که حاصل یک عدد فرد است.

ب) n فرد است، یعنی $\left( k\in \mathbb{N} \right)\,n=2k-1$؛ در این حالت هم داریم:

${{n}^{2}}-5n+7$
$={{\left( 2k-1 \right)}^{2}}-5\left( 2k-1 \right)+7$
$=4{{k}^{2}}-4k+1-10k+5+7$
$=4{{k}^{2}}-14k+13=2\left( 2{{k}^{2}}-7k+6 \right)+1 $

که باز هم حاصل یک عدد فرد است.

به‌عبارت دیگر زوج یا فرد بودن n،‌ فرد بودن ${{n}^{2}}-5n+7$ را نتیجه می‌دهد.

اگر زوج بودن n را با p و فرد بودن n، را با q و فرد بودن ${{n}^{2}}-5n+7$ را با r نمایش دهیم، حکم را می‌توان به‌صورت گزاره $p\vee q\Rightarrow r$ نمایش داد. با توجه به هم‌ارزی بودن $p\vee q\Rightarrow r\equiv \left( p\Rightarrow r \right)\wedge \left( q\Rightarrow r \right)$ شیوهٔ اثبات در مثال فوق توجیه می‌شود.

به طریق مشابه، برای هر تعداد متناهی گزارهٔ دلخواه داریم:

${{P}_{1}}\vee {{P}_{2}}\vee ...{{P}_{n}}\Rightarrow r\equiv \left( {{P}_{1}}\Rightarrow r \right)\wedge \left( {{P}_{2}}\Rightarrow r \right)\wedge ...\left( {{P}_{n}}\Rightarrow r \right)$

نوع دیگر ی از در نظر گرفتن حالت‌های ممکن، در مثال زیر ارائه شده است.

مثال: ثابت کنید اگر a و b دو عدد حقیقی باشند و $ab=0$ آن‌گاه $a=0$ یا $b=0$.

حل: برای a دو حالت ممکن است رخ دهد:

الف) اگر $a=0$، در این حالت حکم برقرار است (چرا؟)
ب) اگر $a\ne 0$، در این حالت ${{a}^{-1}}$ (معکوس a) یک عدد حقیقی است و با ضرب طرفین رابطه $ab=0$ در ${{a}^{-1}}$ داریم:

$ab=0\Rightarrow {{a}^{-1}}\left( ab \right)={{a}^{-1}}\times 0$

بنابراین در هر دو حالت حکم برقرار است.

$\Rightarrow b=0$

اثبات غیرمستقیم

اثبات به روش برهان خلف

در هندسه (1) با اثبات به روش برهان خلف که نوعی اثبات غیرمستقیم است آشنا شده‌اید. در روش برهان خلف فرض می‌کنیم که حکم نادرست باشد و سپس با استفاده از قوانین منطق گزاره‌ها و دنباله‌ای از استدلال‌های درست و مبتنی بر فرض به یک نتیجه غیرممکن یا نتیجه متضاد با فرض می‌رسیم و از آنجا (با توجه به منطقی بودن همه مراحل) معلوم می‌شود که فرضِ نادرست بودنِ حکم باطل است و درستی حکم ثابت می‌گردد.

در تعاملات و محاورات روزمره هم ممکن است از این روش استدلال استفاده کنیم. آنجا که با فردی نظری کاملاً متضاد داریم و به‌درستی نظر خود اطمینان داریم، برای رسیدن به نتیجه مورد نظرمان، موقتاً نظر مخالف خود را می‌پذیریم و با استفاده از دنباله‌ای از استدلال‌ها و ادبیاتی که مورد توافق دو طرف است، نشان می‌دهیم که پذیرفتن نظر او به بن‌بست یا تناقض منجر می‌شود.

مثال: ثابت کنید حاصل جمع یک عدد گویا و یک عدد گنگ، عددی گنگ است.

حل: فرض کنیم که r یک عدد گویا و x یک عدد گنگ باشد. نشان می‌دهیم که $r+x$ یک عدد گنگ است. اگر (فرض خلف) $r+x$ گنگ نباشد، بنابراین عددی گویا است. از طرفی می‌دانیم که تفاضل دو عدد گویا، عددی گویا است. پس تفاضل $r+x$ و r باید عددی گویا باشد یعنی $r+x-r\in Q$ و از آنجا $x\in Q$ که با فرض ما در تناقض است. در نتیجه فرض خلف باطل است و حکم اثبات می‌گردد.

مثال: حاصل ضرب هر عدد گویای ناصفر در یک عدد گنگ، عددی گنگ است.

حل: فرض کنیم r یک عدد گویای ناصفر باشد و x عددی گنگ باشد ولی rx عددی گویا (فرض خلف) باشد. می‌دانیم که حاصل ضرب هر دو عدد گویا، عددی گویاست. علاوه بر این معکوس هر عدد گویای ناصفر هم عددی گویاست. بنابراین $(\frac{1}{r})(rx)\in Q$ و از آن‌جا $x\in Q$ که با فرض در تناقض است.

مثال: ${{a}_{1}}$، ${{a}_{2}}$ و ${{a}_{3}}$ عددهایی صحیح هستند و ${{b}_{1}}$، ${{b}_{2}}$ و ${{b}_{3}}$ هم همان اعداد ولی به‌ترتیب دیگری قرار گرفته‌اند. ثابت کنید $\left( {{a}_{1}}-{{b}_{1}} \right)\left( {{a}_{2}}-{{b}_{2}} \right)\left( {{a}_{3}}-{{b}_{3}} \right)$ عددی زوج است.

حل: برای درک بهتر مسئله، مثالی ارائه ${{a}_{1}}$، ${{a}_{2}}$ و ${{a}_{3}}$ را به‌ترتیب، 5، 8 و 1 در نظر می‌گیریم و ${{b}_{1}}$، ${{b}_{2}}$ و ${{b}_{3}}$ را 8، 1 و 5 در نظر می‌گیریم، داریم:

$\left( {{a}_{1}}-{{b}_{1}} \right)\left( {{a}_{2}}-{{b}_{2}} \right)\left( {{a}_{3}}-{{b}_{3}} \right)=\left( 5-8 \right)\left( 8-1 \right)\left( 1-5 \right)=\left( -3 \right)\left( 7 \right)\left( -4 \right)=84$

اگر $\left( {{a}_{1}}-{{b}_{1}} \right)\left( {{a}_{2}}-{{b}_{2}} \right)\left( {{a}_{3}}-{{b}_{3}} \right)$ زوج نباشد (فرض خلف) پس عددی فرد است. پس هر سه عامل ${{a}_{1}}-{{b}_{1}}$، ${{a}_{2}}-{{b}_{2}}$ و ${{a}_{3}}-{{b}_{3}}$ هم باید فرد باشند (چرا؟) و در نتیجه مجموع آنها هم باید عددی فرد باشد، یعنی $\left( {{a}_{1}}-{{b}_{1}} \right)+\left( {{a}_{2}}-{{b}_{2}} \right)+\left( {{a}_{3}}-{{b}_{3}} \right)$ باید عددی فرد باشد. امّا مجموع این سه عبارت صفر است! 

اثبات‌های بازگشتی/ گزاره‌های هم ارز

اگر ارزش دو گزاره یکسان باشد آنها را گزاره‌های هم‌ارز (هم‌ارزش) می‌نامیم.

اگر P و Q دو گزاره هم‌ارز (یعنی همواره هر دو درست یا هر دو نادرست) باشند، آن‌گاه گزاره‌های $P\Rightarrow Q$ و $Q\Rightarrow P$ هر دو درست هستند و در نتیجه $P\Leftrightarrow Q$ یک گزاره درست است.
به عکس اگر ترکیب دو شرطی $P\Leftrightarrow Q$ درست باشد، آن‌گاه P و Q دو گزاره هم‌ارز خواهند بود و اگر ارزش یکی از آنها را بدانیم، ارزش دیگری نیز همان خواهد بود. به‌کمک این موضوع می‌توانیم درستی یا نادرستی یک گزاره را بررسی کنیم.

در عمل به‌طور معمول درستی یا نادرستی گزاره‌ای که معمولاً ساده‌تر است را انتخاب می‌کنیم. البته این کار ممکن است که در یک مرحله انجام نشود، به‌طور مثال اگر Q ،P و R سه گزاره باشند و $Q\Leftrightarrow R$ و $P\Leftrightarrow Q$ یعنی ارزش سه گزاره یکسان است و اثبات درستی یا نادرستی هر یک، تکلیف دو گزاره دیگر را معلوم خواهد کرد. به هر حال ممکن است این عمل ادامه یابد و در تعدادی متناهی مرحله کار انجام شود.

با توجه به آنچه گفته شد، در هنگام استفاده از این روش اثبات (که گاهی به آن «روش بازگشتی» هم می‌گویند) توانایی ارائه ترکیب دو شرطی درست و مناسب بسیار اساسی است.

مثال: ترکیب دو شرطی $\left( a,b\in \mathbb{R} \right)$، $a=b\Leftrightarrow {{a}^{3}}={{b}^{3}}$ درست است ولی ترکیب دو شرطی $a=b\Leftrightarrow {{a}^{2}}={{b}^{2}}$ درست نیست (چرا؟)

مثال: اگر $a\gt 0$ ثابت کنید $a+\frac{1}{a}\ge 2$

اگر $a\gt 0$، داریم: $a+\frac{1}{a}\ge 2\Leftrightarrow {{a}^{2}}+1\ge 2a$

این ترکیب دو شرطی بیان نمی‌کند که کدام گزاره درست است، بلکه تنها بیانگر آن است که دو گزاره هم‌ارز هستند و اثبات هر کدام، دیگری را نتیجه می‌دهد. به نظر شما چرا این دو گزاره هم‌ارز هستند؟ اثبات کدام یک ساده‌تر است؟
همچنین

${a^2} + 1 \ge 2a \Leftrightarrow {a^2} + 1 - 2a \ge 0$

و در نهایت: 

${{a}^{2}}+1-2a\ge 0\Leftrightarrow {{\left( a-1 \right)}^{2}}\ge 0$

آخرین گزاره یعنی ${{\left( a-1 \right)}^{2}}\ge 0$ همواره برقرار است، به‌عبارت دیگر حکم هم‌ارز گزاره‌ای است که همواره برقرار است.

پس حکم ثابت شده است. مراحل اثبات را (با شرط $a\gt 0$) به‌صورت زیر می‌توان خلاصه کرد:

$a + \frac{1}{a} \ge 2 \Leftrightarrow {a^2} + 1 \ge 2a$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow {a^2} + 1 - 2a \ge 0$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow {\left( {a - 1} \right)^2} \ge 0$ همواره برقرار است

به هر حال این نوع استدلال در گفت‌وگوها و مذاکرات معمول هم مورد استفاده قرار می‌گیرد، آنجا که برای بررسی یک حکم، معادل آن‌را به مخاطب یادآوری می‌کنیم و از عباراتی نظیر: آنچه که شما می‌گویید معادل این است که …، یا گفته شما به مثابه آن است که …، در آنجا باید از قوانین و ادبیات مورد پذیرش طرفین پیروی کنیم و در ریاضیات از منطق ریاضی. در هر حال در هنگام استفاده از این نوع استدلال در زندگی روزمره هم ممکن است پس از چند مرحله به نتیجه برسیم.

مثال: ثابت کنید میانگین حسابی دو عدد نامنفی، از میانگین هندسی آنها کمتر نیست.

حل: اگر a و b دو عدد نامنفی باشند، حکم ما چنین خواهد بود: $\frac{a+b}{2}\ge \sqrt{ab}$

$\frac{a+b}{2}\ge \sqrt{ab}\Leftrightarrow a+b\ge 2\sqrt{ab}$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow a+b-2\sqrt{ab}\ge 0$
$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow {{\left( \sqrt{a}- \sqrt{b} \right)}^{2}}\ge 0$ گزاره همیشه درست

مثال: اگر a و b دو عدد حقیقی باشند ثابت کنید:

${{a}^{2}}+ab+{{b}^{2}}\ge 0$

حل:

${{a}^{2}}+ab+{{b}^{2}}\ge 0\Leftrightarrow {{(a+\frac{b}{2})}^{2}}+\frac{3{{b}^{2}}}{4}\ge 0$

اثبات کوتاه و زیبایی است. حکم با یک گزاره همیشه درست (سمت راست) هم‌ارز است.

راه دوم:

$ {{a}^{2}}+ab+{{b}^{2}}\ge 0\Leftrightarrow 2{{a}^{2}}+2ab+2{{b}^{2}}\ge 0$
$ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow {{a}^{2}}+{{b}^{2}}+2ab+{{a}^{2}}+{{b}^{2}}\ge 0$
$ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \Leftrightarrow {{\left( a+b \right)}^{2}}+{{a}^{2}}+{{b}^{2}}\ge 0$ گزاره همیشه درست است

البته ممکن است شما هم راه حل دیگری برای این مسئله ارائه کنید.
شیوه‌ای که در این قسمت از درس مورد استفاده قرار گرفت را برای نشان دادن نادرستی یک گزاره نیز می‌توان به‌کار برد.